1. Field of the Invention
The present invention relates to a bridge for use in a network containing a redundant route caused by a plurality of bridges and a route change method of the network using the same.
2. Description of the Related Art
In a network containing a redundant route caused by a plurality of bridges, a spanning tree protocol is employed for determining a route.
For example, as shown in FIG. 15, assume a network over which LAN 1 and LAN 2 are connected to each other by means of a bridge A.
Here, in the case of a network over which node “n1” such as personal computer is connected to LAN 1, and HUB 1 is connected to LAN 2, packets transmitted from the node “n1” are transmitted to all nodes of a broadcast domain including node “n2” such as personal computer connected to the HUB 1 via LAN 1→bridge A→LAN 2→HUB 1.
Over such network, when HUB 2 is connected to LAN 1 and LAN 2 in parallel to bridge A, a packet transmitted from the node “n1” loops over the network like LAN 1→bridge A→LAN 2→HUB 2→LAN 1→bridge A→LAN 2→HUB 2. As a result, a packet cannot be transmitted from a node other than node “n1” (node in a broadcast domain other than node “n1”).
In the case where a network is configured by only bridge A and HUB 1 as shown in FIG. 15, a spanning tree is employed to prevent a packet transmitted from a node from looping over the network.
In addition, as shown in FIG. 16, in the case where two bridges A and B are connected in parallel between LAN 1 to which node “n1” such as personal computer is connected and LAN 2 to which HUB 1 is connected, thereby making communication among nodes “n2”, “n3”, “n4”, . . . such as personal computers connected to node “n1” and HUB 1, one bridge is generally used to make communication. When this bridge A is linked down, the other bridges B is used to make communication, whereby a spanning tree is employed in order to cause a network to provide redundancy.
Here, basic algorithm and protocol of the spanning tree consists of the following items (1) to (5) (Refer to ISO/IEC 15802-3; 1998 (E) ANSI/IEEE Std 802. 1D, 1998 Edition, Part 3: Media Access Control (MAC) Bridges, pp v-xix, LOCAL AND METROPOLITAN AREA NETWORKS: 8. The Spanning Tree Algorithm and Protocol pp. 58-109 and 9. Encoding of Bridge Protocol Data Units (BPDUs) pp. 110-113).
(1) A special frame called Configuration Bridge Protocol Data Units (hereinafter, referred to as BPDU) is exchanged between bridges.
The following works are performed based on this exchanged BPDU.
(2) A network root bridge is selected.
Only one root bridge exists in the entire LAN bridge connected.
(3) Each bridge computes the shortest route that reaches a root bridge (A port that provides the shortest route to the root bridge is called a root port).
(4) With respect to each LAN, a “designated bridge” is selected from a bridge connected to the LAN.
(5) Each bridge selects a port (designated port) that belongs to a spanning tree and a port (blocking port) that does not belong to such spanning tree.
All data frames received at a blocking port are discarded.
In addition, frame transmission from a blocking port is not performed at all.
A received BPDU is not forwarded at all.
A data portion of the above mentioned BPDU includes at least root ID, bridge ID, root path cost.
Root ID is an ID of a root bridge (or a bridge assumed to be such root bridge), and is generated based on a MAC address of such bridge and a priority designated by an administrator.
Bridge ID is an ID of a bridge that transmits a BPDU, and is generated based on a MAC address of such bridge and a priority designated by an administrator.
A root path cost is a cost of the (possible) shortest route from a bridge that transmits a BPDU to a root bridge.
In an initial state (when a power is supplied), each bridge is a root bridge itself, and it is assumed that a root path cost is 0.
Each bridge transmits the initial value of a BPDU to all ports, and at the same time, receives the BPDU transmitted from another bridge from all the ports.
In the case where a bridge has received a better BPDU from a port, such bridge stops transmission of BPDU to that port, and then, changes the value of the BPDU to be transmitted by its own bridge.
In this manner, in the case where a spanning tree enters a stable state, only one bridge transmits a BPDU among each LAN.
For example, in the case where BPDU 1 and BPDU 2 are present, it is judged which of the above BPDUs is better in accordance with rules (1) to (4) below.
(1) In the case where root ID of BPDU 1 is numerically smaller than that of BPDU 2, it is judged that BPDU 1 is better than BPDU 2.
(2) In the case where root ID of BPDU 1 is numerically equal to that of BPDU 2, if a root path cost of BPDU 1 is smaller than that of BPDU 2, it is judged that BPDU 1 is better than BPDU 2.
(3) In the case where root ID of BPDU 1 is numerically equal to that of BPDU 2, and a root path cost of BPDU 1 is equal to that of BPDU 2, if bridge ID of BPDU 1 is numerically smaller than that of BPDU 2, it is judged that BPDU 1 is better than BPDU 2.
(4) In the case where root ID of BPDU 1 is numerically equal to that of BPDU 2, a root path cost of BPDU 1 is equal to that of BPDU 2, and bridge ID of BPDU 1 is numerically equal to that of BPDU 2, if port ID of BPDU 1 is smaller than that of BPDU 2, it is judged that BPDU 1 is better than BPDU 2.
Then, each bridge compares the initial value of its own BPDU with that of the BPDU from another bridge received from all ports, and selects root ID from the best BPDU.
Next, each bridge computes its own root path cost in accordance with (root path cost)=(root path cost in the best BPDU)+path cost.
A path cost is a cost to the root that each port individually has, and the value of the cost can be set by an administrator.
Once a root ID, a route port, and a root path cost are defined, each bridge updates the content of BPDU transmitted by such each bridge itself.
Further, its own updated BPDU is compared with BPDU received from a port other than root port, and it is judged whether or not each port other than root port is a designated bridge itself.
A port that is a designated bridge is called a designated port, and a port that is not a designated bridge is called a blocking port.
In BPDU transmission and data frame forwarding to a root port, a designated port and a blocking port, a data frame is forwarded at the root port without transmitting BPDU; BPDU is transmitted, and a data frame is forwarded at the designated port; and BPDU is not transmitted, and a data frame is not forwarded at the blocking port.
In this manner, once a spanning tree is configured, each bridge performs regular operations described in (1) to (4) below.
These regular operations are required for reconfiguring a spanning tree that has been configured due to a bridge fault or addition of new bridge.
(1) BPDU includes an element called “message age”.
This value denotes an elapsed time after a root bridge has generated a BPDU that corresponds to the above BPDU.
(2) A root bridge transmits its own BPDU periodically to all ports. At this time, “message age” is set to 0.
(3) Each bridge stores a received BPDU, and increases the value of the “message age” of the BPDU stored in each port with an elapse of time (message age timer).
(4) A bridge other than root bridge transmits its own BPDU when it receives a BPDU from a root port.
At this time, as a value of the “message age”, there is used a value equal to or greater than the “message age” of the root port and greater than the “message age” of the received BPDU.
Here, the reconfiguration of the spanning tree occurs in any of the cases described in (1) and (2) below.
(1) In the case where the “message age” timer of the stored BPDU times out (in the case where a max age is exceeded); or
(2) In the case where a BUDU better than that stored in a port is received from the same port.
In the case where any of the above events occurs, a bridge performs re-computation for a root ID, a root cost, and a root port.
In the meantime, it is very dangerous to perform data frame transmission before all the bridges over a network enters a normal state after configuration (reconfiguration) of a spanning tree has been started.
This is because there is a possibility that a temporary loop occurs during spanning tree configuration. Therefore, even if each bridge determines its own designated port, it does not start data frame forwarding immediately.
There are three types of the states of each port in a bridge:
(1) listening: No work concerning a data frame is carried out.
(2) learning: Although the learning of a source MAC address is performed, forwarding is not performed.
(3) forwarding: Data frame forwarding is performed.
The lengths of the listening state and learning state are called a “forward delay”. A root bridge determines its value, enters its value in a BPDU, and transmits the fact to each bridge.
In addition, a timer employed in the listening state and learning state is called a “forwarding timer”.
If spanning tree reconfiguration occurs, a host position changes, and the contents of an old learning table may be incorrect.
Thus, the bridge corresponding to a spanning tree has two kinds of states as timeout values of the learning table aging timer as follows.
(1) Normal value: This value is set to a long time such as a few minutes.
(2) A value used after topology change: This value is the same as the forward delay value.
When a bridge senses spanning tree reconfiguration, the timeout value of the learning table aging timer is set to a value identical to forward delay for a predetermined period of time.
In the meantime, a spanning tree algorithm and protocol has a system that notifies to all bridges that spanning tree reconfiguration has occurred.
(1) When a bridge senses a topology change, that bridge transmits a frame called TCN-BPDU (Topology Change Notification BPDU) to a root port with hello time intervals.
This transmission is continued until a BPDU in which a TCA (Topology Change Acknowledgment) flag is set has been received from the root port.
(2) A bridge which has received TCN-BPDU also transmits TCN-BPDU to its own root port.
On the other hand, to a port that has received a TCN-BPDU, a BPDU TCA flag is set, and a BPDU is transmitted during transmission of the next BPDU.
(3) In the case where a root bridge receives a TCN-BPDU or the state of its own port changes, the root bridge transmits a BPDU in which a TC (Topology Change) flag is set from that time to a max age+forward delay time.
(4) A bridge which has received the TC flag set BPDU from a root port sets a TC flag for its own BPDU, and transmits such BPDU. This transmission is continued until a BPDU in which a TC flag is not set has been received.
(5) While a bridge receives TC flag set BPDU from the root port, the bridge uses the value of “forward delay” as a timeout value of the learning table aging timer.
In this way, a spanning tree has an algorithm for automatically removing a loop in a redundant bridge network, and automatically sensing a network topology change caused by a device fault or cable failure, thereby automatically changing a network topology so as to prevent a loop from being produced.
In the meantime, such spanning tree works so as not to form a loop in a network. However, in the case where a root port is linked down for any reason (such as cable reconnection, invalid port setting or communication route change caused by a communication failure, for example), an operation for restoring a blocking port that has stopped and reconfiguring a spanning tree is executed.
FIG. 17 shows an example of a network describing such operation.
In the network shown in FIG. 17, assume that three bridges A, B and C are connected to each other, and a spanning tree is configured so that, in a normal state, communication can be made when bridge A is defined as a root bridge, bridge B is defined as a representative bridge, and a port of bridge C oriented to the bridge B is defined as a blocking port.
With respect to the nodes connected to each bridge, only portions required for illustration is illustrated, and the other portion is omitted.
In the network shown in FIG. 17, in the case of making communication between node “n1” connected to bridge B and node “n2” connected to bridge C, a signal from the node “n1” of bridge B is transmitted to node “n2” of bridge C through bridges A and C.
If communication is disabled between bridges A and B for any reason, communication between node “n1” connected to bridge B and node “n2” connected to bridge C is also disabled. Thus, it is required to open a blocking port of bridge C, and change a communication route, thereby reconfiguring a spanning tree.
In a conventional spanning tree, if communication is disabled between bridges A and B, bridge B does not receive a BPDU periodically transmitted from bridge A that is a root bridge. In this manner, when bridge B does not receive the BPDU for a predetermined time, bridge B detects a network failure relevant to bridge A.
When bridge B detects a network failure, a BPDU is not transmitted from bridge B to bridge C.
In this manner, bridge C does not receive a BPDU essentially transmitted via bridges A and B.
When bridge C starts an operation for gradually opening a blocking port so as to enable communication between bridges B and C after an elapsed time from a time when a BPDU is not received from bridge B has elapsed a predetermined designated time.
When a blocking port of bridge C fully opens, communication between a node connected bridge B and a node connected to bridge C is enabled.
In this manner, in the network by bridges, as an algorithm and a protocol standardized for employing a redundant configuration, there is known ANSI/IEEE 802. 1D, 1998 Edition, 8. Spanning Tree Algorithm and Protocol pp. 58-109 and 9. Encoding of Bridge Protocol Data Units (BPDUs) pp. 110-113 as described above.
In this IEEE 802. 1D, 1998 Edition, 8. Spanning Tree Algorithm and Protocol pp. 58-109 and 9. Encoding of Bridge Protocol Data Units (BPDUs) pp. 110-113, a route change operation is performed after at least 6 seconds of the period when BPDU has not been received from a representative port due to a route failure.
Thus, during real-time communication or the like, a communication disable time occurs for 14 second in total including the above 6 seconds and twice forward delay times (at least 4 seconds).
For example, when a video or the like is distributed, the video is interrupted for this communication disable time so that the accurate video cannot be distributed for the time.
Further, when a plurality of bridges using this algorithm and protocol are connected to each other, thereby configure a network, up to 7 bridges can be connected to each other and more than 7 bridges cannot be connected to each other to configure the network.
The inventors etc. of the present application have already disclosed the invention relating to “spanning tree bridge and route change method thereof” for fast reconfiguration in U.S. Pat. Appln. Publication No. US2001/0021177A1 (filing date Mar. 5, 2001) in order to eliminate the above problem.
When a link down is sensed at a root port, the bridge disclosed in this U.S. Pat. Appln. Publication No. US2001/0021177A1 performs topology sensing processing and enters a root bridge like when an effective period of time of a BPDU has lapsed, that is at the time when the max age timer comes through.
Also when a BPDU having root bridge information inferior to root bridge information held by a reception port has been received from a representative bridge, the bridge performs the topology change sensing processing and enters a root bridge like when the max age timer comes through.
Thus, when the bridge has entered a root bridge, a port which has been essentially a blocking port is immediately transited to a forwarding state.
A bridge which has received TCN-BPDU immediately propagates TCN-BPDU regardless of hold time.
When the bridge is a root bridge, the bridge immediately transmits a BPDU in which a TC sensing flag is set to all the ports.
The bridge which has received a BPDU in which a TC sensing flag is set immediately transmits a BPDU regardless of hold time, and immediately after, deletes database information of a forwarding table.
Therefore, according to the configuration disclosed in U.S. Pat. Appln. Publication No. US2001/0021177A1, in the network containing a redundant route caused by a plurality of bridges, it is possible to handle cable reconnection, invalid port setting, or communication route change due to a communication failure, and promote a return from communication interruption thereby reducing route change time.
However, also in the configuration disclosed in U.S. Pat. Appln. Publication No. US2001/0021177A1 described above, there are problems described later.
As shown in FIG. 18, a case where a plurality of bridges 11 are connected to each other in multi-stages in a ring shape so that a network 13 is configured will be considered.
Here, in order to simplify the description, as shown in FIG. 18, there will be described a configuration example of the network 13 where twelve bridges 11 (A to L) are connected to each other between ports 12 in a ring shape, a node 14 (X) is connected to a bridge A and a node 14 (Y) is connected to a bridge H.
Here, assume that bridge A is a root bridge, connecting ports 12 (12g) of bridges G and F are in a blocking state.
In this case, a packet from the node X to the node Y reaches the node Y through the bridges A→L→K→J→I→H.
Now, when a failure is present in the route between the bridges A and L, according to the configuration disclosed in U.S. Pat. Appln. Publication No. US2001/0021177A1, the bridge L enters a root bridge to transmit a BPDU to the bridge K.
Then, the bridge K performs port cost addition of a BPDU to the bridge J and transmits the same. Further, a BPDU in which port cost addition has been performed is transmitted from the bridge J to the bridge I.
After a BPDU has been received from the previous bridge and port cost addition processing has been performed, when an operation of transmitting a BPDU to the next bridge is repeated and the BPDU has finally reached the bridge G, the bridge G transits the port 12g from a blocking state to a forwarding state.
Thus, a packet from the node X to the node Y is enabled to reach through a new route of the bridges A→B→C→D→E→F→G→H.
At this time, a BPDU from the bridge K is routed through four bridges until the BPDU reaches the bridge G. Thus, assume that a time from the time when one bridge has received a BPDU and recounted the cost to a time when the bridge has output it to another port is set to, for example, 10 msec, 50 msec in total is required.
In the example shown in FIG. 18, the BPDU from the bridge K routes through four bridges until the BPDU bridge K reaches the bridge G. But, for example, in the case of a network configuration where 49 bridges are routed through, 500 msec is required.
Therefore, in the configuration disclosed in such U.S. Pat. Appln. Publication No. US2001/0021177A1, the more the number of bridges increases according to the network configuration, the more the time is required for the route change, and there occurs a problem that lowering of communication efficiency is caused.
Next, the case where a network is configured and a new loop is configured in the network will be considered.
Here, in FIG. 19, there will be described a case where the bridges K and L are connected to each other and a new loop is configured. Also in this case, a root bridge is assumed to be the bridge A like the aforementioned case.
When the bridge K is connected to the bridge J, it enters the port 12 (12k) into a listening state, and starts to transmit a BPDU toward the bridge J. The BPDU which the bridge J has received reaches the bridge G through the bridges I and H.
Here, the bridge G has a port having the highest cost from the bridge A so that the connecting port 12g with the bridge F is immediately entered into a blocking port.
There is a problem that, even when the bridge G has entered the port 12g into a blocking port, the port 12k of the bridge K and the port 12j of the bridge J remain in a listening state.
Therefore, a packet delivery is interrupted in the route of the bridges J, I, and H. The bridge J enters the port 12j into a learning state after a forwarding delay timer has lapsed (for example, 15 seconds in default has been lapsed), and further enters the port 12j into a forwarding state after a forward delay timer has lapsed.
Thus, the packet delivery starts 30 seconds after a loop has been configured. In other words, there is a problem that the packet delivery is delayed for the time of the forwarding delay timer.
In this manner, in the network configuration having a redundant route using conventional bridges, a time is required after a link down at the time of starting up of the network and line failure occurrence has been sensed until blocking ports are opened so that communication between nodes connected to bridges is enabled. Further, a time until communication starts and a time until communication interruption is eliminated are slow, thereby causing lowering of communication efficiency.